// https://leetcode-cn.com/problems/generate-parentheses/
// 22. 括号生成
// 数字 n 代表生成括号的对数，设计一个函数，用于能够生成所有可能并且有效
// 的括号组合。

function generateParenthesis(n: number): string[] {
    const result: string[] = [];

    if (n === 0) return result;

    /**
     * 深度优先产生有效括号
     * @param cur 当前的字符
     * @param left 左括号剩余个数
     * @param right 右括号剩余个数
     * @param ans 结果集
     */
    function dfs(
        cur: string,
        left: number,
        right: number,
        ans: string[]
    ): void {
        if (left === 0 && right === 0) {
            ans.push(cur);
            return;
        }

        if (left > 0) {
            dfs(cur + '(', left - 1, right, ans);
        }

        if (right > 0 && left < right) {
            dfs(cur + ')', left, right - 1, ans);
        }
    }

    dfs('', n, n, result);

    return result;
}
